package roboGP;

import java.util.ArrayList;
import java.util.Random;

/**
 * Un albero di ITreeNode che rappresenta un cromosoma del robot.
*/
public class Tree 
{
	public static enum InitType { GROW, FULL };
	public static enum NodeType { ANY, INTERNAL, LEAF };
	
	public static double INIT_GROW_LEAF_TRESH = 0.3;
	public static double INIT_INTERNAL_COND_ACT_TRESH = 0.7;
	public static double CROSSOVER_INTERNAL_LEAVES_SPLIT = 0.9;
	public static int CROSSOVER_MAX_RANDOM_PICK = 15;
	public static double SUBTREE_MUT_TREE_METHOD_SPLIT = 0.5;
	public static int SUBTREE_MUT_MAX_DEPTH = 3;
	public static int MUTATE_MAX_TRIES = 10;
	
	private ITreeNode _root;
	private int _maxDepth;
	
	/**
	 * Inizializza la classe partendo da un albero di ITreeNode già formato.
	 * @param root La radice dell'albero.
	 * @param maxDepth La profondità massima consentita per l'albero.
	 */
	public Tree(ITreeNode root, int maxDepth)
	{
		_root = root;
		_maxDepth = maxDepth;
	}
	
	/**
	 * Inizializza l'albero in modo casuale.
	 * @param actions Una lista di tutti i possibili ActionNode.
	 * @param conditions Una lista di tutti i possibili ConditionNode.
	 * @param initMaxDepth La profondità massima raggiungibile dall'albero.
	 * @param method Metodo di creazione dell'albero.
	 * @param treeMaxDepth La profondità massima consentita per l'albero.
	 * @throws IllegalArgumentException Se initMaxDepth > treeMaxDepth o se treeMaxDepth < 2.
	 */
	public Tree(ArrayList<String> actions, ArrayList<String> conditions, int initMaxDepth, InitType method, int treeMaxDepth)
	{
		if (initMaxDepth > treeMaxDepth || treeMaxDepth < 2)
			throw new IllegalArgumentException();
		
		_root = randomTreeCreation(actions, conditions, null, initMaxDepth, method);
		_maxDepth = treeMaxDepth;
	}
	
	private ITreeNode randomTreeCreation(ArrayList<String> actions, ArrayList<String> conditions, ITreeNode parent,
			int max_depth, InitType method)
	{
		Random random = new Random();
		ITreeNode node = null;
		if (max_depth == 0 || (method == InitType.GROW && (random.nextDouble() < INIT_GROW_LEAF_TRESH)))
		{
			node = new ActionNode(actions.get(random.nextInt(actions.size())), parent, null);
		}
		else
		{
			if (random.nextDouble() < INIT_INTERNAL_COND_ACT_TRESH)
			{
				node = new ConditionNode();
				ITreeNode leftChild = randomTreeCreation(actions, conditions, node, max_depth - 1, method);
				ITreeNode rightChild = randomTreeCreation(actions, conditions, node, max_depth - 1, method);
				
				node.setJavaCode(conditions.get(random.nextInt(conditions.size())));
				node.setParent(parent);
				((ConditionNode)node).setChildren(leftChild, rightChild);
			}
			else
			{
				node = new ActionNode();
				ITreeNode child = randomTreeCreation(actions, conditions, node, max_depth - 1, method);
				
				node.setJavaCode(actions.get(random.nextInt(actions.size())));
				node.setParent(parent);
				((ActionNode)node).setChild(child);
			}
		}
		return node;
	}
	
	/**
	 * Imposta un nuovo nodo radice, di fatto eliminando il vecchio albero.
	 * @param root La nuova radice dell'albero.
	 */
	public void setRootNode(ITreeNode root)
	{
		_root = root;
	}
	
	/**
	 * Restituisce la pronfondità massima dell'albero.
	 * @return La pronfondità massima dell'albero.
	 */
	public int getMaxDepth()
	{
		return _maxDepth;
	}
	
	/**
	 * Controlla se la profondità attuale dell'albero è maggiore a quella massima impostata.
	 * @return Se la profondità è maggiore di quella consentita.
	 */
	public boolean isOverMaxDepth()
	{
		return getTreeHeight() > _maxDepth;
	}
	
	/**
	 * Calcola l'altezza dell'albero.
	 * @throws IllegalArgumentException Se l'albero non è ben formato.
	 * @return L'altezza dell'albero.
	 */
	public int getTreeHeight()
	{
		return recGetHeight(_root);
	}
	
	private static int recGetHeight(ITreeNode node)
	{
	    if (node instanceof ActionNode) 
	    {
	        if (((ActionNode)node).hasChild())
	        {
	        	return 1 + recGetHeight(((ActionNode)node).getChild());
	        }
	        else
		    	return 0;
	    }
	    else if (node instanceof ConditionNode) 
	    {
	    	return 1 + Math.max(recGetHeight(((ConditionNode)node).getLeftChild()), 
	    			recGetHeight(((ConditionNode)node).getRightChild()));
	    }
	    throw new IllegalArgumentException();
	}
	
	/**
	 * Restituisce il numero di nodi nell'albero.
	 * @return Il numero di nodi nell'albero.
	 */
	public int nodeCount()
	{
		return nodeCountBytype().getGlobalCount();
	}
	
	private TreeVisitCounter nodeCountBytype()
	{
		TreeVisitCounter counter = new TreeVisitCounter();
		recNodeCount(_root, counter);
		return counter;
	}

	private void recNodeCount(ITreeNode node, TreeVisitCounter counter)
	{
	    if (node instanceof ActionNode) 
	    {
	        if (((ActionNode)node).hasChild())
	        {
	        	recNodeCount(((ActionNode)node).getChild(), counter);
	        	counter.incrementInternals();
	        }
	        else
		    	counter.incrementLeaves();
	    }
	    else if (node instanceof ConditionNode) 
	    {
	    	recNodeCount(((ConditionNode)node).getLeftChild(), counter);
	    	recNodeCount(((ConditionNode)node).getRightChild(), counter);
        	counter.incrementInternals();
	    }
	}

	private class TreeVisitCounter
	{
		private int _internals;
		private int _leaves;
		
		public TreeVisitCounter()
		{
			_internals = _leaves = 0;
		}
		public int getInternalNodes()
		{
			return _internals;
		}
		public void incrementInternals()
		{
			_internals++;
		}
		public int getLeaves()
		{
			return _leaves;
		}
		public void incrementLeaves()
		{
			_leaves++;
		}
		public int getGlobalCount()
		{
			return _internals + _leaves;
		}
	}
	
	/**
	 * Cerca e restituisce l'n-esimo nodo incontrato in una visita in pre-order dell'albero.
	 * @param n L'indice del nodo da restituire.
	 * @throws IndexOutOfBoundsException Se n è maggiore del numero dei nodi dell'albero.
	 * @throws IllegalArgumentException Se l'albero non è ben formato.
	 * @return Il nodo corrispondente all'indice.
	 */
	public ITreeNode getNodeByIndexPreOrder(int n)
	{
		return getNodeByIndexPreOrder(n, NodeType.ANY);
	}

	/**
	 * Cerca e restituisce l'n-esimo nodo, specificando se nodo interno o foglia, incontrato in una visita 
	 * in pre-order dell'albero.
	 * @param n L'indice del nodo da restituire.
	 * @param type Il tipo del nodo da ricercare.
	 * @throws IndexOutOfBoundsException Se n è maggiore del numero dei nodi del tipo specificato.
	 * @throws IllegalArgumentException Se l'albero non è ben formato.
	 * @return Il nodo corrispondente all'indice.
	 */
	public ITreeNode getNodeByIndexPreOrder(int n, NodeType type)
	{
		ITreeNode tmp = recGetNodeByIndexPreOrder(_root, new TreeVisitCounter(), n, type);
		if (tmp == null)
			throw new IndexOutOfBoundsException();
		return tmp;
	}
	
	private ITreeNode recGetNodeByIndexPreOrder(ITreeNode node, TreeVisitCounter i, int target, NodeType type)
	{		
		if ((type == NodeType.ANY && i.getGlobalCount() == target) 
				|| (type == NodeType.LEAF && i.getLeaves() == target 
						&& (node instanceof ActionNode && !((ActionNode)node).hasChild()))
				|| (type == NodeType.INTERNAL && i.getInternalNodes() == target
						&& (node instanceof ConditionNode || (node instanceof ActionNode && ((ActionNode)node).hasChild()))))
		{
				return node;
		}
		else if ((type == NodeType.ANY && i.getGlobalCount() < target) || (type == NodeType.LEAF && i.getLeaves() <= target)
				|| (type == NodeType.INTERNAL && i.getInternalNodes() <= target))
		{
		    if (node instanceof ActionNode) 
		    {
		    	if (((ActionNode)node).hasChild())
		    	{
		    		i.incrementInternals();
		    		return recGetNodeByIndexPreOrder(((ActionNode)node).getChild(), i, target, type);
		    	}
		    	else
		    	{
		    		i.incrementLeaves();
		    		return null;
		    	}
		    }
		    else if (node instanceof ConditionNode) 
		    {
	    		i.incrementInternals();
		    	ITreeNode tmp =	recGetNodeByIndexPreOrder(((ConditionNode)node).getLeftChild(), i, target, type);
		    	if (tmp == null)
		    		return recGetNodeByIndexPreOrder(((ConditionNode)node).getRightChild(), i, target, type);
		    	else 
		    		return tmp;
		    }
		}
		// non dovrebbe mai accadere
		throw new IllegalArgumentException();
	}
	
	/**
	 * Crea un nuovo albero in cui un nodo è mutato in uno dello stesso tipo.
	 * @param actions Una lista di tutti i possibili ActionNode.
	 * @param conditions Una lista di tutti i possibili ConditionNode.
	 * @return L'albero con la mutazione.
	 */
	public Tree mutate(ArrayList<String> actions, ArrayList<String> conditions)
	{
		Tree mutatedTree = this.copy();
		
		int mutatingIndex = (int) (Math.random() * mutatedTree.nodeCount());
		ITreeNode mutatingNode = mutatedTree.getNodeByIndexPreOrder(mutatingIndex);
		
		String mutation = null;
		int i = 0;
		if (mutatingNode instanceof ActionNode)
		{
			do
			{
				int mutationIndex =  (int) (Math.random() * actions.size());
				mutation = actions.get(mutationIndex);
				i++;
				if (i >= MUTATE_MAX_TRIES)
				{
					mutation = actions.get((actions.indexOf(mutationIndex) + 1) % actions.size());
					break;
				}
			} while (mutatingNode.getJavaCode().equals(mutation));
		}
		else if (mutatingNode instanceof ConditionNode)
		{
			i = 0;
			do
			{
				int mutationIndex =  (int) (Math.random() * conditions.size());
				mutation = conditions.get(mutationIndex);
				i++;
				if (i >= MUTATE_MAX_TRIES)
				{
					mutation = conditions.get((conditions.indexOf(mutationIndex) + 1) % conditions.size());
					break;
				}
			} while (mutatingNode.getJavaCode().equals(mutation));
		}
		mutatingNode.setJavaCode(mutation);
		
		return mutatedTree;
	}
	
	/**
	 * Crea un nuovo albero in cui un sottoalbero è mutato in un nuovo sottoalbero, generato in modo casuale
	 * con lo stesso metodo del costruttore random, scegliendo casualmente anche la modalità di riepimento.
	 * Notare che non viene effettuato nessun controllo sulla presenza di una effettiva mutazione: il nuovo
	 * sottoalbero potrebbe anche essere uguale a quello vecchio.
	 * @param actions Una lista di tutti i possibili ActionNode.
	 * @param conditions Una lista di tutti i possibili ConditionNode.
	 * @return L'albero con la mutazione.
	 */
	public Tree subTreeMutate(ArrayList<String> actions, ArrayList<String> conditions)
	{
		Tree mutatedTree = this.copy();
		
		Random random = new Random();

		int mutatingIndex = (int) (random.nextDouble() * mutatedTree.nodeCount());
		ITreeNode mutatingNode = mutatedTree.getNodeByIndexPreOrder(mutatingIndex);
		
		int maxDepth;
		int depthDelta = _maxDepth - mutatingNode.getDepth();
		if (depthDelta > SUBTREE_MUT_MAX_DEPTH)
			maxDepth = (int) (random.nextDouble() * SUBTREE_MUT_MAX_DEPTH);
		else if (depthDelta > 0 && depthDelta < SUBTREE_MUT_MAX_DEPTH)
			maxDepth = (int) (random.nextDouble() * (_maxDepth - mutatingNode.getDepth()));
		else
			return mutate(actions, conditions);
		
		ITreeNode mutatedNode = null;
		if (random.nextDouble() < SUBTREE_MUT_TREE_METHOD_SPLIT)
			mutatedNode = randomTreeCreation(actions, conditions, mutatingNode.getParent(), maxDepth, InitType.GROW);
		else
			mutatedNode = randomTreeCreation(actions, conditions, mutatingNode.getParent(), maxDepth, InitType.FULL);
		
		changeChildNode(mutatedTree, mutatingNode.getParent(), mutatingNode, mutatedNode);
		
		mutatingNode = null;
		
		return mutatedTree;
	}
	
	/**
	 * Sostituisce oldChild con newChild come figlio di parent all'interno dell'albero tree.
	 * @param tree L'albero in cui è contenuto parent.
	 * @param parent Il nodo padre.
	 * @param oldChild Il vecchio nodo figlio.
	 * @param newChild Il nuovo nodo figlio.
	 */
	private static void changeChildNode(Tree tree, ITreeNode parent, ITreeNode oldChild, ITreeNode newChild)
	{
		if (parent == null)
		{
			tree.setRootNode(newChild);
		}
		else if (parent instanceof ActionNode)
		{
			((ActionNode)parent).setChild(newChild);
		}
		else if (parent instanceof ConditionNode)
		{
			if (((ConditionNode)parent).getLeftChild().equals(oldChild))
				((ConditionNode)parent).setLeftChild(newChild);
			else
				((ConditionNode)parent).setRightChild(newChild);
		}

	}
	
	/**
	 * Esegue il crossover tra i due alberi passati come parametri, che vengono modificati.
	 * Il punto di crossover è scelto in modo tale che sia più probabile la scelta di un nodo interno.
	 * @param first Un albero.
	 * @param second Un albero.
	 */
	public static void crossover(Tree first, Tree second)
	{
		Random random = new Random();
		
		TreeVisitCounter firstCounter = first.nodeCountBytype();
		TreeVisitCounter secondCounter = second.nodeCountBytype();
		
		// stabilisce se il punto di crossover deve essere una foglia o un nodo interno
		boolean internalSplit = random.nextDouble() < CROSSOVER_INTERNAL_LEAVES_SPLIT 
				&& firstCounter.getInternalNodes() > 0
				&& secondCounter.getInternalNodes() > 0;
		
		ITreeNode firstCrossoverPoint = null;
		ITreeNode secondCrossoverPoint = null;

		if (internalSplit)
		{		
			int firstCrossPointDepth;
			int secondCrossPointDepth;
			int firstCrossPointHeight;
			int secondCrossPointHeight;

			int i = 0;
			do
			{
				i++;
				if (i < CROSSOVER_MAX_RANDOM_PICK)
				{
					int crossoverIndex = (int) (random.nextDouble() * firstCounter.getInternalNodes());
					firstCrossoverPoint = first.getNodeByIndexPreOrder(crossoverIndex, NodeType.INTERNAL);

					crossoverIndex = (int) (random.nextDouble() * secondCounter.getInternalNodes());
					secondCrossoverPoint = second.getNodeByIndexPreOrder(crossoverIndex, NodeType.INTERNAL);
				}
				else
				{
					// gioca sul fatto che entrambi gli alberi hanno la stessa altezza massima
					// viene scelto di norma il secondo nodo interno come punto di crossover
					// esluso nel caso in cui l'unico nodo interno è la radice.
					int crossoverIndex;
					if (firstCounter.getInternalNodes() > 1)
						crossoverIndex = 1;
					else
						crossoverIndex = 0;
					firstCrossoverPoint = first.getNodeByIndexPreOrder(crossoverIndex, NodeType.INTERNAL);

					if (secondCounter.getInternalNodes() > 1)
						crossoverIndex = 1;
					else
						crossoverIndex = 0;
					secondCrossoverPoint = second.getNodeByIndexPreOrder(crossoverIndex, NodeType.INTERNAL);
					break;
				}

				firstCrossPointHeight = recGetHeight(firstCrossoverPoint);
				secondCrossPointHeight = recGetHeight(secondCrossoverPoint);
				firstCrossPointDepth = firstCrossoverPoint.getDepth();
				secondCrossPointDepth = secondCrossoverPoint.getDepth();
			} while (!((firstCrossPointDepth <= second.getMaxDepth() - secondCrossPointHeight)
					&& (secondCrossPointDepth <= first.getMaxDepth() - firstCrossPointHeight)));
		}
		else
		{
			int crossoverIndex = (int) (random.nextDouble() * firstCounter.getLeaves());
			firstCrossoverPoint = first.getNodeByIndexPreOrder(crossoverIndex, NodeType.LEAF);

			crossoverIndex = (int) (random.nextDouble() * secondCounter.getLeaves());			
			secondCrossoverPoint = second.getNodeByIndexPreOrder(crossoverIndex, NodeType.LEAF);
		}

				
		ITreeNode firstOldParent = firstCrossoverPoint.getParent();
		ITreeNode secondOldParent = secondCrossoverPoint.getParent();
		
		firstCrossoverPoint.setParent(secondOldParent);
		secondCrossoverPoint.setParent(firstOldParent);
		
		changeChildNode(first, firstOldParent, firstCrossoverPoint, secondCrossoverPoint);
		changeChildNode(second, secondOldParent, secondCrossoverPoint, firstCrossoverPoint);	
	}
	
	/**
	 * Elimina tutti i nodi a profondità maggiore di quella massima impostata per l'albero.
	 * Nel caso in cui un ConditionNode si trovasse senza figli per via di questa eliminazione
	 * viene sostituito con la foglia più a sinistra del sottoalbero radicato in esso.
	 * @throws IllegalArgumentException Se l'albero non è ben formato.
	 */
	public void prune()
	{
		recPrune(_root, 0);
	}
	
	private boolean recPrune(ITreeNode node, int level)
	{
		if (level == _maxDepth + 1)
		{			
			if (node.getParent() instanceof ActionNode)
			{
				changeChildNode(this, node.getParent(), node, null);
			}
			else if (node.getParent() instanceof ConditionNode)
			{
				changeChildNode(this, node.getParent().getParent(), node.getParent(), findFirstLeaf(node.getParent()));
			}	
			return true;
		}
				
		if (node instanceof ActionNode)
		{
			if (((ActionNode)node).hasChild())
				recPrune(((ActionNode)node).getChild(), level + 1);
		}
		else if (node instanceof ConditionNode)
		{
			if (!recPrune(((ConditionNode)node).getLeftChild(), level + 1))
				recPrune(((ConditionNode)node).getRightChild(), level + 1);
		}
		return false;
	}
	
	private ITreeNode findFirstLeaf(ITreeNode node)
	{
		if (node instanceof ActionNode)
		{
			if (((ActionNode)node).hasChild())
				return findFirstLeaf(((ActionNode)node).getChild());
			else
				return node;
		}
		else if (node instanceof ConditionNode)
			return findFirstLeaf(((ConditionNode)node).getLeftChild());
		
		// non dovrebbe mai accadere
		throw new IllegalArgumentException();
	}
	
	/**
	 * Converte l'albero nel codice Java corrispondente.
	 * @param Il livello di itentazione del codice.
	 * @return Il codice Java.
	 */
	public String toJavaCode(int ident)
	{
	    ArrayList<String> out = new ArrayList<String>();
	    
	    String tabs = "";
	    for (int i = 0; i < ident; i++)
	    	tabs = tabs + "\t";
	    
	    nodeToCode(_root, out, tabs);
	    
	    StringBuilder sb = new StringBuilder();
	    for (String str : out)
	    	sb.append(str);
	    
	    return sb.toString();
	}

	private void nodeToCode(ITreeNode node, ArrayList<String> out, String tabs) 
	{

	    if (node instanceof ActionNode) 
	    {
	        out.add(tabs + node.getJavaCode() + ";\n");
	        if (((ActionNode)node).hasChild())
	            nodeToCode(((ActionNode)node).getChild(), out, tabs);
	    }
	    else if (node instanceof ConditionNode) 
	    {
	        out.add(tabs + "if (" + node.getJavaCode() + ") { \n");
	        nodeToCode(((ConditionNode)node).getLeftChild(), out, tabs + "\t");
	        out.add(tabs + "} \n" + tabs + "else { \n");
	        nodeToCode(((ConditionNode)node).getRightChild(), out, tabs + "\t");
	        out.add(tabs + "}\n");
	    }
	}
	
	/**
	 * Crea una copia dell'albero.
	 * @throws IllegalArgumentException Se l'albero non è ben formato.
	 * @return Una copia dell'albero.
	 */
	public Tree copy()
	{
		return new Tree(copyTraversal(_root), _maxDepth);
	}
	
	private ITreeNode copyTraversal(ITreeNode treeNode)
	{
		if (treeNode instanceof ActionNode)
		{
			ActionNode node = (ActionNode)treeNode;
			if (node.hasChild())
			{
				ITreeNode copiedChild = copyTraversal(node.getChild());
				ActionNode copied = new ActionNode( node.getJavaCode(), null, copiedChild);
				copiedChild.setParent(copied);
				return copied;
			}
			else
			{
				return new ActionNode(node.getJavaCode(), null, null);
			}
		}
		else if (treeNode instanceof ConditionNode)
		{
			ConditionNode node = (ConditionNode)treeNode;
			if (node.hasChildren())
			{
				ITreeNode copiedLeftChild = copyTraversal(node.getLeftChild());
				ITreeNode copiedRightChild = copyTraversal(node.getRightChild());
				ConditionNode copied = new ConditionNode(node.getJavaCode(), null,
						copiedLeftChild, copiedRightChild);
				copiedLeftChild.setParent(copied);
				copiedRightChild.setParent(copied);
				return copied;
			}
			else
			{
				// non dovrebbe mai accadere
				throw new IllegalArgumentException();
			}
		}
		// non dovrebbe mai accadere
		throw new IllegalArgumentException();
		
	}

}
